/*
 * @lc app=leetcode.cn id=239 lang=typescript
 *
 * [239] 滑动窗口最大值
 */

// @lc code=start
function maxSlidingWindow(nums: number[], k: number): number[] {
  // 单调队列
  const dequeue: number[] = [];
  const ans: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    // 入队
    while (dequeue.length && nums[i] > nums[dequeue[dequeue.length - 1]]) {
      dequeue.pop();
    }
    dequeue.push(i);
    // 超出窗口大小，队首出队
    if (i - dequeue[0] === k) dequeue.shift();
    if (i + 1 < k) continue;

    ans.push(nums[dequeue[0]]);
  }

  return ans;
}
// @lc code=end
